package main.leetcode.clockin.Auguest;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 336. 回文对
 *
 * <p>给定一组唯一的单词， 找出所有不同 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
 *
 * <p>示例 1: 输入: ["abcd","dcba","lls","s","sssll"] 输出: [[0,1],[1,0],[3,2],[2,4]] 解释: 可拼接成的回文串为
 * ["dcbaabcd","abcddcba","slls","llssssll"]
 *
 * <p>示例 2: 输入: ["bat","tab","cat"] 输出: [[0,1],[1,0]] 解释: 可拼接成的回文串为 ["battab","tabbat"]
 */
public class day6 {
    public static void main(String[] args) {
        System.out.println(
                new day6().palindromePairs(new String[] {"abcd", "dcba", "lls", "s", "sssll"}));
        System.out.println(new day6().palindromePairs(new String[] {"bat", "tab", "cat"}));
    }
    /** 暴力 */
    public List<List<Integer>> palindromePairs(String[] words) {
        if (words == null || words.length < 2) {
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        int n = words.length;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (j == i) {
                    continue;
                }
                if (validatePalindrome(words[i] + words[j])) {
                    res.add(Arrays.asList(i, j));
                }
            }
        }
        return res;
    }

    private boolean validatePalindrome(String s) {
        StringBuilder tmp = new StringBuilder(s);
        return s.equals(tmp.reverse().toString());
    }
}
